A technique for searching a route that avoids heavy traffic at an intersection has been proposed recently. For example, JP 2009-180500A and JP 2012-3343A disclose techniques that set different costs in one road district between intersections with regard to each exit direction or each approach direction. These techniques set different costs to one road, for example, in the case of turning right and in the case of going straight. This allows for search of a route that avoids right-turn congestion in the region of left-hand traffic.